SK Telecom ditubuhkan pada bulan Mac 1984 dengan nama Korea Mobile Telecommunications Services Co., tetapi dinamai semula sebagai Korea Mobile Telecommunications Corp. (KMT) pada bulan Mei 1988. Pada bulan Jun 1994, Kumpulan SK menjadi pemegang saham KMT yang terbesar. KMT menyertai Kumpulan SK secara rasmi pada bulan Januari 1997 dan menukarkan namanya menjadi SK Telecom pada bulan Mac tahun tersebut.

Pada bulan Oktober 2000, SK Telecom menjadi pengendali yang kedua di dunia selepas DoCoMo, milikan NTT, untuk melancarkan sebuah perkhidmatan 3G komersil yang menggunakan teknologi WCDMA. Ini diikuti oleh pelancaran rangkaian 1xEV-DO CDMA2000 yang pertama di dunia pada bulan Januari 2002. Teknologi ini amat meningkatkan laju penghantaran data.

Pada bulan Mei 2005, SK Telecom memutuskan untuk menjual 60% daripada saham SK Teletechnya kepada Pantech Curitel. SK Teletech kemudian menggantikan jenamanya menjadi "SKY" pada tahun 2006, dengan jenama tersebut masih merupakan jenama premium barisan telefon bimbit untuk Pantech Curitel.